/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if (head==NULL) return NULL;
        RandomListNode *x=head;
        while (x!=NULL) {
            RandomListNode *y=new RandomListNode(x->label);
            y->next=x->next;
            x->next=y;
            x=x->next->next;
        }
        x=head;
        while (x!=NULL) {
            if (x->random==NULL)
                x->next->random=NULL;
            else
                x->next->random=x->random->next;
            x=x->next->next;
        }
        RandomListNode *ansHead=NULL, *ansTail=NULL;
        x=head;
        while (x!=NULL) {
            if (ansTail==NULL) {
                ansHead=ansTail=x->next;
            } else {
                ansTail->next=x->next;
                ansTail=x->next;
            }
            x->next=x->next->next;
            x=x->next;
            ansTail->next=NULL;
        }
        return ansHead;
    }
};
